home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CUJ9102.ARJ / 9N02039A < prev    next >
Text File  |  1992-07-06  |  6KB  |  228 lines
  1.  
  2. Listing 4.
  3.  
  4. /* sltest.c */
  5.  
  6. #define SLTEST  1
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <setjmp.h>
  10. #include "skiplist.h"
  11.  
  12. /* globals */
  13.  
  14. int listsize;   /* size of our test list */
  15. int maxlevel = MAXLEVEL;
  16. int partition;
  17. int *emptr; /* dynamic array of list elements */
  18. int nnodes; /* count of nodes allocated */
  19. long ctotals;   /* total number of comparisons */
  20. int comps;  /* temporary counter */
  21. int mincomps;
  22. int maxcomps;
  23. #define COMPMAX 80  /* width of screen */
  24. int compary[COMPMAX] = { 0 };   /* for graph routine */
  25. int overflow = 0;
  26. int levels[MAXLEVEL] = { 0 };
  27. jmp_buf errbuf; /* short circuit when out of memory */
  28. NODE *testlist;
  29. int orderflag;  /* non-zero for random insertions */
  30. #define SL_RAND_MAX 32767
  31.  
  32. int intcmp(a, b)    /* test comparison routine */
  33. KEYTYPE a, b;
  34. {
  35.     comps += 1; /* track length of search path */
  36.     if(a < b)
  37.         return(-1);
  38.     else if(a == b)
  39.         return(0);
  40.     else
  41.         return(1);
  42. }
  43.  
  44. main(argc, argv)
  45. int argc;
  46. char *argv[];
  47. {
  48.     if(argc < 6)
  49.         usage();
  50.     if((listsize = atoi(argv[i])) < 1)
  51.         usage();
  52.     if(listsize > SL_RAND_MAX)
  53.     {
  54.         listsize = SL_RAND_MAX;
  55.         printf("listsize reduced to %d\n", SL_RAND_MAX);
  56.     }
  57.     if((maxlevel = atoi(argv[2])) < 1)
  58.         usage();
  59.     if(maxlevel > MAXLEVEL)
  60.     {
  61.         maxlevel = MAXLEVEL;
  62.         printf("maxlevel reduced to %d\n", MAXLEVEL);
  63.     }
  64.     if((partition = atoi(argv[3])) < 1)
  65.         || (partition >= maxlevel))
  66.     {
  67.         usage();
  68.     }
  69.     slsrand((unsigned) atoi(argv[4]));
  70.     orderflag = atoi(argv[5]);
  71.  
  72.     list_init();
  73.     list_build();
  74.     list_test();
  75.     list_stats();
  76.     exit(EXIT_SUCCESS);
  77. }
  78.  
  79. usage() /* describe command line errors */
  80. {
  81.     printf("\nUsage:\t");
  82.     printf("sltest <size> <maxlevel> <partition> <seed> <flag>\n");
  83.     printf("\t<size> of test list (>= 1)\n");
  84.     printf("\t<maxlevel> max number of pointers per node (>= 1)\n");
  85.     printf("\t<partition> (>= 1 && < maxlevel [= %d])\n", maxlevel);
  86.     printf("\t<seed> for the random number generator\n");
  87.     printf("\t<flag> 0 for in-order insertions, otherwise random");
  88.     exit(EXIT_FAILURE);
  89. }
  90.  
  91. list_init()
  92. {
  93.     if((emptr = (int *) calloc(listsize, sizeof(int)))
  94.         == NULL)
  95.     {
  96.         nomem();
  97.     }
  98.     if((testlist = newlist()) == NIL)
  99.         nomem();
  100. }
  101.  
  102. nomem()
  103. {
  104.     printf("Not enough memory for a list of size %u\n",
  105.         (unsigned)listsize);
  106.     exit(EXIT_FAILURE);
  107. }
  108.  
  109. list_build()
  110. {
  111.     unsigned slrand();
  112.     unsigned i;
  113.  
  114.     if(setjmp(errbuf))
  115.         listsize = nnodes;  /* largest possible */
  116.     else if(orderflag == 0)
  117.     {
  118.         for(nnodes = 0, i = 1; i <= listsize; )
  119.             insert(testlist, i++);
  120.     }
  121.     else
  122.     {
  123.         for(nnodes = 0; nnodes < listsize; )
  124.             insert(testlist, slrand());
  125.     }
  126. }
  127.  
  128. list_test()
  129. {
  130.     int i;
  131.  
  132.     ctotals = 0L;
  133.     mincomps = listsize;
  134.     maxcomps = 0;
  135.     for(i = 0, comps = 0; i < listsize; ++i, comps = 0)
  136.     {
  137.         search(testlist, emptr[i]);
  138.         ctotals += (long) comps;
  139.         if(comps < mincomps)
  140.             mincomps = comps;
  141.         else if(comps > maxcomps)
  142.             maxcomps = comps;
  143.         if(comps < COMPMAX)
  144.             compary[comps] += 1;
  145.         else
  146.             overflow += 1;  /* won't fit on screen */
  147.     }
  148. }
  149.  
  150. /* for computing behavior of balanced trees */
  151. unsigned treelevels[] = {
  152.     1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
  153.     11, 12, 13, 14, 15, 16 };
  154. unsigned powersof2[] = {
  155.     1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
  156.     4096, 8192, 16384, (SL_RAND_MAX + 1) };
  157. int depth;
  158. long accumulator;
  159.  
  160. list_stats()    /* print out statistics */
  161. {
  162.     int i;
  163.     int scale;
  164.     int temp;
  165.     int cmax;
  166.  
  167.     printf("\nskiplist size = %d", listsize);
  168.     printf("\npointers per level = ");
  169.     for(i = 0; i < maxlevel; i += 1)
  170.         printf("%d ", levels[i]);
  171.     printf("\ncomparisons per search:  ");
  172.     printf("mean = %.3f, minimum = %d, maximum = %d\n",
  173.         ((float)ctotals) / ((float)listsize),
  174.         mincomps, maxcomps);
  175.     if(overflow != 0)   /* graph won't fit on screen */
  176.         printf("distribution of comparisons overflows buffer\n");
  177.     else
  178.     {
  179.         cmax = 0;
  180.         for(i = mincomps; i <= maxcomps; i += 1)
  181.         {
  182.             if(compary[i] > cmax)
  183.                 cmax = compary[i];
  184.         }
  185.         scale = cmax / 10;
  186.         if(scale == 0)  /* watch out for cmax < 10!! */
  187.             scale = 1;
  188.         temp = cmax % 10;
  189.         if((temp / scale) > 5)
  190.             scale += 1;
  191.         for(temp = cmax; temp >= 0; temp -= scale)
  192.         {
  193.             if(temp <= scale)   /* last pass through */
  194.                 if(scale > 1)   /* make sure we */
  195.                     temp = 1;   /* print all */
  196.             for(i = mincomps; i <= maxcomps; i += 1)
  197.             {
  198.                 if(compary[i] / temp)
  199.                     printf("*");
  200.                 else
  201.                     printf(" ");
  202.             }
  203.             printf("\n");
  204.         }
  205.         printf("distribution from minimum through maximum:");
  206.         printf("  scale = %d:1\n", scale);
  207.     }
  208.     for(i = 0; (powersof2[i] - 1) < listsize; i += 1)
  209.         ;
  210.     depth = i--;    /* maximum for perfectly balanced tree */
  211.     accumulator = ((long) treelevels[i])
  212.         * ((listsize - powersof2[i--]) + 1);
  213.     while(i >= 0)
  214.     {
  215.         accumulator += (long) (treelevels[i]
  216.             * powersof2[i--]);
  217.     }
  218.     printf("for perfect trees:  ");
  219.     printf("mean = %.3f, minimum = 1, maximum = %d\n",
  220.         (((float)accumulator) / ((float)listsize)), depth);
  221.     printf("for degenerate trees:  ");
  222.     printf("mean = %.3f, minimum = 1, maximum = %d\n",
  223.         ((float) (listsize + 1) / 2), listsize);
  224. }
  225.  
  226. /* EOF */
  227.  
  228.